/*******************************************************************************
 * Copyright (c) 2013 Olli Alm / Metropolia www.metropolia.fi
 * 
 * Permission is hereby granted, free of charge, to any person obtaining
 * a copy of this software and associated documentation files (the
 * "Software"), to deal in the Software without restriction, including
 * without limitation the rights to use, copy, modify, merge, publish,
 * distribute, sublicense, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so, subject to
 * the following conditions:
 * 
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 ******************************************************************************/
package fi.metropolia.mediaworks.juju.util;
//package pt.tumba.spell;
import java.util.List;
import java.util.Vector;


/**
 *  Implementation of a Ternary Search Trie, a data structure for storing <code>String</code> objects
 *  that combines the compact size of a binary search tree with the speed of a digital search trie, and is 
 *  therefore ideal for practical use in sorting and searching data.</p> <p>
 * 
 *  This data structure is faster than hashing for many typical search problems, and supports
 *  a broader range of useful problems and operations. Ternary searches are faster than
 *  hashing and more powerful, too.</p> <p>
 * 
 *  The theory of ternary search trees was described at a symposium in 1997 (see "Fast 
 *  Algorithms for Sorting and Searching Strings," by J.L. Bentley and R. Sedgewick,
 *  Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, January 1997).
 *  Algorithms in C, Third Edition, by Robert Sedgewick (Addison-Wesley, 1998) provides 
 *  yet another view of ternary search trees. 
 * 
 * @author Bruno Martins
 *
 */
public class TernarySearchTrie<A> {

	/**
	 *  An inner class of Ternary Search Trie that represents a node in the trie.
	 */
	protected final class TSTNode<B> {

		/** Index values for accessing relatives array. */
		protected final static int PARENT = 0, LOKID = 1, EQKID = 2, HIKID = 3;

		/** The key to the node. */
		protected A data;

		/** The relative nodes. */
		@SuppressWarnings("unchecked")
		protected TSTNode<B>[] relatives = new TSTNode[4];

		/** The char used in the split. */
		protected char splitchar;

		/**
		 *  Constructor method.
		 *
		 *@param  splitchar  The char used in the split.
		 *@param  parent     The parent node.
		 */
		protected TSTNode(char splitchar, TSTNode<B> parent) {
			this.splitchar = splitchar;
			relatives[PARENT] = parent;
		}
	}


	/**
	 *  Compares characters by alfabetical order.
	 *
	 *@param  cCompare2  The first char in the comparison.
	 *@param  cRef      The second char in the comparison.
	 *@return           A negative number, 0 or a positive number if the second
	 *      char is less, equal or greater.
	 */
	private static int compareCharsAlphabetically(int cCompare2, int cRef) {
		int cCompare = 0;
		if (cCompare2 >= 65) {
			if (cCompare2 < 89) {
				cCompare = (2 * cCompare2) - 65;
			} else if (cCompare2 < 97) {
				cCompare = cCompare2 + 24;
			} else if (cCompare2 < 121) {
				cCompare = (2 * cCompare2) - 128;
			} else
				cCompare = cCompare2;
		} else
			cCompare = cCompare2;
		if (cRef < 65) {
			return cCompare - cRef;
		}
		if (cRef < 89) {
			return cCompare - ((2 * cRef) - 65);
		}
		if (cRef < 97) {
			return cCompare - (cRef + 24);
		}
		if (cRef < 121) {
			return cCompare - ((2 * cRef) - 128);
		}
		return cCompare - cRef;
	}

	/**  The default number of values returned by the <code>matchAlmost</code> method. */
	private int defaultNumReturnValues = -1;

	/** the number of differences allowed in a call to the <code>matchAlmostKey</code> method. */
	private int matchAlmostDiff;

	/** The base node in the trie. */
	private TSTNode<A> rootNode;

	/**
	 *  Constructs an empty Ternary Search Trie.
	 */
	public TernarySearchTrie() {
	}

	/**
	 *  Deletes the node passed in as an argument. If this node
	 *  has non-null data, then both the node and the data will be deleted. It also
	 *  deletes any other nodes in the trie that are no longer needed after the
	 *  deletion of the node.
	 *
	 *@param  nodeToDelete  The node to delete.
	 */
	private void deleteNode(TSTNode<A> nodeToDelete) {
		if (nodeToDelete == null) {
			return;
		}
		nodeToDelete.data = null;
		while (nodeToDelete != null) {
			nodeToDelete = deleteNodeRecursion(nodeToDelete);
			//deleteNodeRecursion(nodeToDelete);
		}
	}

	/**
	 *  Recursivelly visits each node to be deleted.
	 * 
	 *  To delete a node, first set its data to null, then pass it into this method,
	 *  then pass the node returned by this method into this method (make
	 *  sure you don't delete the data of any of the nodes returned from this
	 *  method!) and continue in this fashion until the node returned by this
	 *  method is <code>null</code>.
	 * 
	 *  The TSTNode instance returned by this method will be next node to
	 *  be operated on by <code>deleteNodeRecursion</code> (This emulates recursive 
	 *  method call while avoiding the JVM overhead normally associated
	 *  with a recursive method.)
	 *
	 *@param  currentNode  The node to delete.
	 *@return   The next node to be called in deleteNodeRecursion.
	 */
	private TSTNode<A> deleteNodeRecursion(TSTNode<A> currentNode) {
		if (currentNode == null) { return null; }
		if (currentNode.relatives[TSTNode.EQKID] != null || currentNode.data != null) {
			return null;
		}
		// can't delete this node if it has a non-null eq kid or data
		TSTNode<A> currentParent = currentNode.relatives[TSTNode.PARENT];
		boolean lokidNull = currentNode.relatives[TSTNode.LOKID] == null;
		boolean hikidNull = currentNode.relatives[TSTNode.HIKID] == null;
		int childType;
		if (currentParent.relatives[TSTNode.LOKID] == currentNode) {
			childType = TSTNode.LOKID;
		} else if (currentParent.relatives[TSTNode.EQKID] == currentNode) {
			childType = TSTNode.EQKID;
		} else if (currentParent.relatives[TSTNode.HIKID] == currentNode) {
			childType = TSTNode.HIKID;
		} else {
			rootNode = null;
			return null;
		}
		if (lokidNull && hikidNull) {
			currentParent.relatives[childType] = null;
			return currentParent;
		}
		if (lokidNull) {
			currentParent.relatives[childType] =
				currentNode.relatives[TSTNode.HIKID];
			currentNode.relatives[TSTNode.HIKID].relatives[TSTNode.PARENT] =
				currentParent;
			return currentParent;
		}
		if (hikidNull) {
			currentParent.relatives[childType] =
				currentNode.relatives[TSTNode.LOKID];
			currentNode.relatives[TSTNode.LOKID].relatives[TSTNode.PARENT] =
				currentParent;
			return currentParent;
		}
		int deltaHi =
			currentNode.relatives[TSTNode.HIKID].splitchar
				- currentNode.splitchar;
		int deltaLo =
			currentNode.splitchar
				- currentNode.relatives[TSTNode.LOKID].splitchar;
		int movingKid;
		TSTNode<A> targetNode;
		if (deltaHi == deltaLo) {
			if (Math.random() < 0.5) {
				deltaHi++;
			} else {
				deltaLo++;
			}
		}
		if (deltaHi > deltaLo) {
			movingKid = TSTNode.HIKID;
			targetNode = currentNode.relatives[TSTNode.LOKID];
		} else {
			movingKid = TSTNode.LOKID;
			targetNode = currentNode.relatives[TSTNode.HIKID];
		}
		while (targetNode.relatives[movingKid] != null) {
			targetNode = targetNode.relatives[movingKid];
		}
		targetNode.relatives[movingKid] = currentNode.relatives[movingKid];
		currentParent.relatives[childType] = targetNode;
		targetNode.relatives[TSTNode.PARENT] = currentParent;
		if (!lokidNull) {
			currentNode.relatives[TSTNode.LOKID] = null;
		}
		if (!hikidNull) {
			currentNode.relatives[TSTNode.HIKID] = null;
		}
		return currentParent;
	}


	/**
	 *  Retrieve the object indexed by a key.
	 *
	 *@param      key  A <code>String</code> index.
	 *@return      The object retrieved from the Ternary Search Trie.
	 */
	public A get(String key) {
		TSTNode<A> node = getNode(StringUtils.toLowerCase(key.trim(), false));
		if (node == null) { return null; }
		return node.data;
	}

	/**
	 *  Returns the key that indexes the node argument.
	 *
	 *@param  node  The node whose index is to be calculated.
	 *@return  The <code>String</code> that indexes the node argument.
	 */
	protected String getKey(TSTNode<A> node) {
		StringBuffer getKeyBuffer = new StringBuffer();
		getKeyBuffer.setLength(0);
		getKeyBuffer.append("" + node.splitchar);
		TSTNode<A> currentNode;
		TSTNode<A> lastNode;
		currentNode = node.relatives[TSTNode.PARENT];
		lastNode = node;
		while (currentNode != null) {
			if (currentNode.relatives[TSTNode.EQKID] == lastNode) {
				getKeyBuffer.append("" + currentNode.splitchar);
			}
			lastNode = currentNode;
			currentNode = currentNode.relatives[TSTNode.PARENT];
		}
		getKeyBuffer.reverse();
		return getKeyBuffer.toString();
	}

	/**
	 *  Returns the node indexed by key, or <code>null</code> if that node doesn't exist.
	 *  Search begins at root node.
	 *
	 *@param  key  A <code>String</code> that indexes the node that is returned.
	 *@return   The node object indexed by key. This object is an
	 *      instance of an inner class named <code>TernarySearchTrie.TSTNode</code>.
	 */
	public TSTNode<A> getNode(String key) {
		return getNode(key, rootNode);
	}

	/**
	 *  Returns the node indexed by key, or <code>null</code> if that node doesn't exist.
	 *  The search begins at root node.
	 *
	 *@param  key2        A <code>String</code> that indexes the node that is returned.
	 *@param  startNode  The top node defining the subtrie to be searched.
	 *@return            The node object indexed by key. This object is
	 *      an instance of an inner class named <code>TernarySearchTrie.TSTNode</code>.
	 */
	protected TSTNode<A> getNode(String key2, TSTNode<A> startNode) {
		String key = StringUtils.toLowerCase(key2.trim(), false);
		if (key == null || startNode == null || key.length() == 0) {
			return null;
		}
		TSTNode<A> currentNode = startNode;
		int charIndex = 0;
		while (true) {
			if (currentNode == null) {
				return null;
			}
			int charComp =
				compareCharsAlphabetically(
					key.charAt(charIndex),
					currentNode.splitchar);
			if (charComp == 0) {
				charIndex++;
				if (charIndex == key.length()) {
					return currentNode;
				}
				currentNode = currentNode.relatives[TSTNode.EQKID];
			} else if (charComp < 0) {
				currentNode = currentNode.relatives[TSTNode.LOKID];
			} else {
				currentNode = currentNode.relatives[TSTNode.HIKID];
			}
		}
	}

	/**
	 *  Returns the node indexed by key, creating that node if it doesn't exist,
	 *  and creating any required intermediate nodes if they don't exist.
	 *
	 *@param  key                           A <code>String</code> that indexes the node that is returned.
	 *@return                                  The node object indexed by key. This object is an
	 *                                               instance of an inner class named <code>TernarySearchTrie.TSTNode</code>.
	 *@exception  NullPointerException      If the key is <code>null</code>.
	 *@exception  IllegalArgumentException  If the key is an empty <code>String</code>.
	 */
	protected TSTNode<A> getOrCreateNode(String key)
		throws NullPointerException, IllegalArgumentException {
		if (key == null) {
			throw new NullPointerException("attempt to get or create node with null key");
		}
		if (key.length() == 0) {
			throw new IllegalArgumentException("attempt to get or create node with key of zero length");
		}
		if (rootNode == null) {
			rootNode = new TSTNode<A>(key.charAt(0), null);
		}
		TSTNode<A> currentNode = rootNode;
		int charIndex = 0;
		while (true) {
			int charComp =
				compareCharsAlphabetically(
					key.charAt(charIndex),
					currentNode.splitchar);
			if (charComp == 0) {
				charIndex++;
				if (charIndex == key.length()) {
					return currentNode;
				}
				if (currentNode.relatives[TSTNode.EQKID] == null) {
					currentNode.relatives[TSTNode.EQKID] =
						new TSTNode<A>(key.charAt(charIndex), currentNode);
				}
				currentNode = currentNode.relatives[TSTNode.EQKID];
			} else if (charComp < 0) {
				if (currentNode.relatives[TSTNode.LOKID] == null) {
					currentNode.relatives[TSTNode.LOKID] =
						new TSTNode<A>(key.charAt(charIndex), currentNode);
				}
				currentNode = currentNode.relatives[TSTNode.LOKID];
			} else {
				if (currentNode.relatives[TSTNode.HIKID] == null) {
					currentNode.relatives[TSTNode.HIKID] =
						new TSTNode<A>(key.charAt(charIndex), currentNode);
				}
				currentNode = currentNode.relatives[TSTNode.HIKID];
			}
		}
	}

	/**
	 *  Returns a <code>List</code> of keys that almost match the argument key. Keys returned
	 *  will have exactly diff characters that do not match the target key,
	 *  where diff is equal to the last value passed in as an argument to the
	 *  <code>setMatchAlmostDiff</code> method.
	 * <p>
	 *  If the <code>matchAlmost</code> method is called before the <code>setMatchAlmostDiff</code> method has
	 * been called for the first time, then diff = 0.
	 *
	 *@param  key  The target key.
	 *@return      A <code>List</code> with the results.
	 */
	public List<String> matchAlmost(String key) {
		return matchAlmost(key, defaultNumReturnValues);
	}

	/**
	 *  Returns a <code>List</code> of keys that almost match the argument key. Keys returned
	 *  will have exactly diff characters that do not match the target key,
	 *  where diff is equal to the last value passed in as an argument to the
	 *  <code>setMatchAlmostDiff</code> method.
	 * <p>
	 *  If the <code>matchAlmost</code> method is called before the <code>setMatchAlmostDiff</code> method has
	 * been called for the first time, then diff = 0.
	 *
	 *@param  key              The target key.
	 *@param  numReturnValues  The maximum number of values returned by this method.
	 *@return                  A <code>List</code> with the results
	 */
	protected List<String> matchAlmost(String key, int numReturnValues) {
		return matchAlmostRecursion(
			rootNode,
			0,
			matchAlmostDiff,
			key,
			((numReturnValues < 0) ? -1 : numReturnValues),
			new Vector<String>(),
			false);
	}



	/**
	 *  Recursivelly vists the nodes in order to find the ones that almost match a given key.
	 *
	 *@param  currentNode                 The current node.
	 *@param  charIndex                     The current char.
	 *@param  d                                 The number of differences so far.
	 *@param  matchAlmostNumReturnValues  The maximum number of values in the result <code>List</code>.
	 *@param  matchAlmostResult2       The results so far.
	 *@param  upTo                             If true all keys having up to and including matchAlmostDiff
	 *                                                   mismatched letters will be included in the result (including
	 *                                                   a key that is exactly the same as the target string) otherwise
	 *                                                   keys will be included in the result only if they have exactly
	 *                                                   matchAlmostDiff number of mismatched letters.
	 *@param  matchAlmostKey           The key being searched.
	 *@return                                      A <code>List</code> with the results.
	 */
	private List<String> matchAlmostRecursion(
		TSTNode<A> currentNode,
		int charIndex,
		int d,
		String matchAlmostKey,
		int matchAlmostNumReturnValues,
		List<String> matchAlmostResult2,
		boolean upTo) {
		if ((currentNode == null)
			|| (matchAlmostNumReturnValues != -1
				&& matchAlmostResult2.size() >= matchAlmostNumReturnValues)
			|| (d < 0)
			|| (charIndex >= matchAlmostKey.length())) {
			return matchAlmostResult2;
		}
		int charComp =
			compareCharsAlphabetically(
				matchAlmostKey.charAt(charIndex),
				currentNode.splitchar);
		List<String> matchAlmostResult = matchAlmostResult2;
		if ((d > 0) || (charComp < 0)) {
			matchAlmostResult =
				matchAlmostRecursion(
					currentNode.relatives[TSTNode.LOKID],
					charIndex,
					d,
					matchAlmostKey,
					matchAlmostNumReturnValues,
					matchAlmostResult,
					upTo);
		}
		int nextD = (charComp == 0) ? d : d - 1;
		boolean cond = (upTo) ? (nextD >= 0) : (nextD == 0);
		if ((matchAlmostKey.length() == charIndex + 1)
			&& cond
			&& (currentNode.data != null)) {
			matchAlmostResult.add(getKey(currentNode));
		}
		matchAlmostResult =
			matchAlmostRecursion(
				currentNode.relatives[TSTNode.EQKID],
				charIndex + 1,
				nextD,
				matchAlmostKey,
				matchAlmostNumReturnValues,
				matchAlmostResult,
				upTo);
		if ((d > 0) || (charComp > 0)) {
			matchAlmostResult =
				matchAlmostRecursion(
					currentNode.relatives[TSTNode.HIKID],
					charIndex,
					d,
					matchAlmostKey,
					matchAlmostNumReturnValues,
					matchAlmostResult,
					upTo);
		}
		return matchAlmostResult;
	}

	/**
	 *  Returns an alphabetical <code>List</code> of all keys in the trie that begin with a given prefix.
	 *  Only keys for nodes having non-null data are included in the <code>List</code>.
	 *
	 *@param  prefix  Each key returned from this method will begin with the characters in prefix.
	 *@return         A <code>List</code> with the results.
	 */
	public List<String> matchPrefix(String prefix) {
		return matchPrefix(prefix, defaultNumReturnValues);
	}

	/**
	 *  Returns an alphabetical <code>List</code> of all keys in the trie that begin with a
	 *  given prefix. Only keys for nodes having non-null data are included in the <code>List</code>.
	 *
	 *@param  prefix           Each key returned from this method will begin with the characters in prefix.
	 *@param  numReturnValues  The maximum number of values returned from this method.
	 *@return                  A <code>List</code> with the results
	 */
	public List<String> matchPrefix(String prefix, int numReturnValues) {
		Vector<String> sortKeysResult = new Vector<String>();
		TSTNode<A> startNode = getNode(prefix);
		if (startNode == null) {
			return sortKeysResult;
		}
		if (startNode.data != null) {
			sortKeysResult.addElement(getKey(startNode));
		}
		return sortKeysRecursion(
			startNode.relatives[TSTNode.EQKID],
			((numReturnValues < 0) ? -1 : numReturnValues),
			sortKeysResult);
	}

	/**
	 *  Returns the number of nodes in the trie that have non-null data.
	 *
	 *@return    The number of nodes in the trie that have non-null data.
	 */
	public int numDataNodes() {
		return numDataNodes(rootNode);
	}

	/**
	 *  Returns the number of nodes in the subtrie below and including the
	 *  starting node. The method counts only nodes that have non-null data.
	 *
	 *@param  startingNode  The top node of the subtrie. the node that defines the subtrie.
	 *@return               The total number of nodes in the subtrie.
	 */
	protected int numDataNodes(TSTNode<A> startingNode) {
		return recursiveNodeCalculator(startingNode, true, 0);
	}

	/**
	 *  Returns the total number of nodes in the trie. The method counts nodes whether
	 *  or not they have data.
	 *
	 *@return    The total number of nodes in the trie.
	 */
	public int numNodes() {
		return numNodes(rootNode);
	}

	/**
	 *  Returns the total number of nodes in the subtrie below and including the 
	 *  starting Node. The method counts nodes whether or not they have data.
	 *
	 *@param  startingNode  The top node of the subtrie. The node that defines the subtrie.
	 *@return               The total number of nodes in the subtrie.
	 */
	protected int numNodes(TSTNode<A> startingNode) {
		return recursiveNodeCalculator(startingNode, false, 0);
	}

	/**
	 *  Stores a value in the trie. The value may be retrieved using the key.
	 *
	 *@param  key    A <code>String</code> that indexes the object to be stored.
	 *@param  value  The object to be stored in the Trie.
	 */
	public void put(String key, A value) {
		getOrCreateNode(StringUtils.toLowerCase(key.trim(), false)).data = value;
	}

	/**
	 *  Recursivelly visists each node to calculate the number of nodes.
	 *
	 *@param  currentNode  The current node.
	 *@param  checkData    If true we check the data to be different of <code>null</code>.
	 *@param  numNodes2    The number of nodes so far.
	 *@return              The number of nodes accounted.
	 */
	private int recursiveNodeCalculator(
		TSTNode<A> currentNode,
		boolean checkData,
		int numNodes2) {
		if (currentNode == null) {
			return numNodes2;
		}
		int numNodes =
			recursiveNodeCalculator(
				currentNode.relatives[TSTNode.LOKID],
				checkData,
				numNodes2);
		numNodes =
			recursiveNodeCalculator(
				currentNode.relatives[TSTNode.EQKID],
				checkData,
				numNodes);
		numNodes =
			recursiveNodeCalculator(
				currentNode.relatives[TSTNode.HIKID],
				checkData,
				numNodes);
		if (checkData) {
			if (currentNode.data != null) {
				numNodes++;
			}
		} else {
			numNodes++;
		}
		return numNodes;
	}

	/**
	 *  Removes the value indexed by key. Also removes all nodes that are rendered
	 *  unnecessary by the removal of this data.
	 *
	 *@param  key  A <code>string</code> that indexes the object to be removed from the Trie.
	 */
	public void remove(String key) {
		deleteNode(getNode(StringUtils.toLowerCase(key.trim(), false)));
	}

	/**
	 *  Sets the number of characters by which words can differ from target word
	 *  when calling the <code>matchAlmost</code> method.
	 * <p>
	 *  Arguments less than 0 will set the char difference to 0, and arguments greater 
	 *  than 3 will set the char difference to 3.
	 *
	 *@param  diff  The number of characters by which words can differ from target word.
	 */
	public void setMatchAlmostDiff(int diff) {
		if (diff < 0) {
			matchAlmostDiff = 0;
		} else if (diff > 3) {
			matchAlmostDiff = 3;
		} else {
			matchAlmostDiff = diff;
		}
	}

	/**
	 *  Sets the default maximum number of values returned from the <code>matchPrefix</code> and
	 *  <code>matchAlmost</code> methods.
	 *  <p>
	 *  The value should be set this to -1 to get an unlimited number of return
	 *  values. note that the methods mentioned above provide overloaded
	 *  versions that allow you to specify the maximum number of return
	 *  values, in which case this value is temporarily overridden.
	 *
	 **@param  num  The number of values that will be returned when calling the
	 *                       methods above.
	 */
	public void setNumReturnValues(int num) {
		defaultNumReturnValues = (num < 0) ? -1 : num;
	}

	/**
	 *  Returns keys sorted in alphabetical order. This includes the start Node and all
	 *  nodes connected to the start Node. 
	 *  <p>
	 *  The number of keys returned is limited to numReturnValues. To get a list that
	 *  isn't limited in size, set numReturnValues to -1.
	 *
	 *@param  startNode        The top node defining the subtrie to be searched.
	 *@param  numReturnValues  The maximum number of values returned from this method.
	 *@return                  A <code>List</code> with the results.
	 */
	protected List<String> sortKeys(TSTNode<A> startNode, int numReturnValues) {
		return sortKeysRecursion(
			startNode,
			((numReturnValues < 0) ? -1 : numReturnValues),
			new Vector<String>());
	}

	/**
	 *  Returns keys sorted in alphabetical order. This includes the current Node and all
	 *  nodes connected to the current Node.
	 *  <p>
	 *  Sorted keys will be appended to the end of the resulting <code>List</code>. The result may be
	 *  empty when this method is invoked, but may not be <code>null</code>.
	 *
	 *@param  currentNode              The current node.
	 *@param  sortKeysNumReturnValues  The maximum number of values in the result.
	 *@param  sortKeysResult2           The results so far.
	 *@return   A <code>List</code> with the results.
	 */
	private List<String> sortKeysRecursion(
		TSTNode<A> currentNode,
		int sortKeysNumReturnValues,
		List<String> sortKeysResult2) {
			
		if (currentNode == null) {
			return sortKeysResult2;
		}
				
		List<String> sortKeysResult =
			sortKeysRecursion(
				currentNode.relatives[TSTNode.LOKID],
				sortKeysNumReturnValues,
				sortKeysResult2);
		if (sortKeysNumReturnValues != -1
			&& sortKeysResult.size() >= sortKeysNumReturnValues) {
			return sortKeysResult;
		}
		if (currentNode.data != null) {
			sortKeysResult.add(getKey(currentNode));
		}
		sortKeysResult =
			sortKeysRecursion(
				currentNode.relatives[TSTNode.EQKID],
				sortKeysNumReturnValues,
				sortKeysResult);
		return sortKeysRecursion(
			currentNode.relatives[TSTNode.HIKID],
			sortKeysNumReturnValues,
			sortKeysResult);
	}

}
